#!/usr/bin/env python 
# -*- coding: utf-8 -*-
# @Time    : 2022/9/21 20:40
# @Author  : Junzhao
# @File    : marge+.py
# @Software: PyCharm
def merge(left, right):
    """排序"""
    lp, rp = 0, 0  # 位置指针
    temp_list = []
    while lp < len(left) and rp < len(right):
        if left[lp] < right[rp]:
            temp_list.append(left[lp])
            lp += 1
        else:
            temp_list.append(right[rp])
            rp += 1
    temp_list += left[lp:]
    temp_list += right[rp:]
    return temp_list


def merge_sort(a_list: list):
    if len(a_list) <= 1:
        return a_list
    num = len(a_list) // 2  # 从中间拆成两个子序列
    # 递归
    left = merge_sort(a_list[:num])
    right = merge_sort(a_list[num:])
    return merge(left, right)


if __name__ == '__main__':
    test_list = [1, 3, 34, 56, 73, 45, 12, 45, 65, 23, 33, 24, 67, 99, 87]
    print(merge_sort(test_list))
